
December 2012 - DRAFT

This is part 1 of the "Password Salt" trilogy, which is part of the [EnigmaPosts Enigma Posts] series. Part 2, namely "Password Rehash," will discuss revising the password hash with higher parameters on the fly; and finally, "Password Cipher" which will encrypt the salt, using an AES cipher which is itself password-based :)

This provides a long overdue update to [PasswordHash Password Hash] (2007) from the [EnigmaPrequels Enigma Prequels] series, where that article neglected to add salt, which is an embarassment to whoever wrote that article... which was unfortunately me.

<h4>Introduction</h4>

We know that passwords should never be seen in clear text, or stored as-is in databases; but rather they should be salted and hashed in an irretrievable manner. Traditionally <a href="http://en.wikipedia.org/wiki/MD5">MD5</a> has been used, and <a href="http://en.wikipedia.org/wiki/SHA-2">SHA-2</a> is recommended these days for general hashing. But we'll read that we should use computationally expensive algorithms for password hashing, so that the passwords are harder to crack.

<img align="left" src=""http://media.mercola.com/imageserver/public/2010/August/8.25salt.jpg"> 

Passwords are vital for IT security. So it's not suprising that IT security so often <a href="http://www.dailymail.co.uk/news/article-2123854/1-5million-account-numbers-hacked-Visa-Mastercard-card-data-theft.html">breaks down</a>. 

We aren't suprised to read that the <a href="http://www.dailymail.co.uk/sciencetech/article-2223197/Revealed-The-common-passwords-used-online-year-password-STILL-tops-list.html">most common</a> password is "password", followed by other premium choices such as "123456", "abc123", "letmein" etc. "Password1" also seems popular and is handy for when "password" isn't accepted on its own. Another favourite is "trustme" which is short for "trust me and anybody else." And when a minimum of 8 characters is required, "12345678" certainly fulfils that requirement.

The most secure passwords are no passwords, e.g. using Google Login, Facebook Connect, Mozilla Persona or some such provider. Such an approach simplifies registration, and is the way forward for consumer sites. However for internal enterprise apps, those might not be suitable. Perhaps the reader can recommend an opensource identity solution which one can use to handle passwords et al, in a PCI-compliant fashion? 

If we are lumbered with having to manage passwords, which so most of us enterprise devs seem to be, then apparently we should add salt. 

<h4>Background reading</h4>

(Please note i have sometimes edited and paraphrased the sources for brevity.)

From http://en.wikipedia.org/wiki/SHA-2,

<blockquote>
SHA-2 is a set of cryptographic hash functions (SHA-224, SHA-256, SHA-384, SHA-512) designed by the National Security Agency (NSA) and published in 2001 by the NIST as a U.S. Federal Information Processing Standard.
</blockquote>

From https://www.owasp.org/index.php/Hashing_Java,

<blockquote>
If each password is simply hashed, identical passwords will have the same hash. This has two drawbacks:

1. Due to the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox), the attacker can find a password very quickly especially if the number of passwords the database is large.

2. An attacker can use a list of precomputed hashes (http://en.wikipedia.org/wiki/Rainbow_table) to break passwords in seconds.

In order to solve these problems, a salt can be concatenated to the password before the digest operation.

A salt is a random number of a fixed length. This salt must be different for each stored entry. It must be stored as clear text next to the hashed password.

In this configuration, an attacker must handle a brute force attack on each individual password. The database is now birthday attack and rainbow crack resistant.
</blockquote>

<img src="https://www.owasp.org/skins/monobook/ologo.png">

From https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet,

<blockquote>
General hashing algorithms (eg, MD5, SHA-1/256/512) are not recommended for password storage. Instead an algorithm specifically designed for the purpose should be used such as bcrypt, PBKDF2 or scrypt.
</blockquote>

From http://en.wikipedia.org/wiki/Bcrypt,

<blockquote>
bcrypt is a key derivation function for passwords based on the Blowfish cipher.
</blockquote>

From http://en.wikipedia.org/wiki/PBKDF2,

<blockquote>
PBKDF2 (Password-Based Key Derivation Function 2) is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards (PKCS) series.

PBKDF2 applies a pseudorandom function to the input password along with a salt value, and repeats the process many times. 

The added computational work makes password cracking much more difficult.

Having a salt added to the password reduces the ability to use precomputed hashes (rainbow tables) for attacks.
</blockquote>

From http://en.wikipedia.org/wiki/Scrypt,

<blockquote>
A password-based key derivation function (password-based KDF) is generally designed to be computationally intensive, so that it takes a relatively long time to compute (say on the order of several hundred milliseconds). 

Legitimate users only need to perform the function once per operation (e.g., authentication), and so the time required is negligible. 

However, a brute force attack would likely need to perform the operation billions of times at which point the time requirements become significant and, ideally, prohibitive.
</blockquote>

<h4>Base64</h4>

Since we will be saving password hashes and their salt in our database (i.e. in a table for user logins), we must encode bytes into text. We will use <a href="http://en.wikipedia.org/wiki/Base64">Base64</a>.

For convenience, we introduce methods which delegate to our Base64 codec of choice e.g. from Apache commons, or the built-in Sun one, or some such.
<pre>
public class Base64 {
    
    public static String encode(byte[] bytes) {
        return new BASE64Encoder().encode(bytes);
    }

    public static byte[] decode(String string) {
        try {
            return new BASE64Decoder().decodeBuffer(string);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}
</pre>

<h4>Psuedo salt</h4>

We use <tt>!SecureRandom</tt> to produce our salt.
<pre>
public class PasswordSalts {
    public static final int SALT_LENGTH = 16;    
    
    public static byte[] nextSalt() {
        byte[] salt = new byte[SALT_LENGTH];
        SecureRandom random = new SecureRandom();
        random.nextBytes(salt);
        return salt;
    }    
}
</pre>
where our salt is a 16 byte random number. Sooo easy :)

Let's have a closer look at the encoded salt.
<pre>
    @Test
    public void testSaltEncoding() throws Exception {
        byte[] saltBytes = Passwords.nextSalt();
        String salt = Passwords.encode(saltBytes);
        System.out.println(salt);
        assertEquals(salt.length(), 24);
        assertEquals(salt.substring(22, 24), "==");
    }
</pre>

<pre>
r2tWqOrfKpr64rpOwoRlcw==
</pre>

So apparently a 16 byte array encoded with Base64 yields a 22 character string followed by two characters of padding. 

<h4>Per user salt</h4>

When the user chooses a password, we generate some salt, hash the password using the salt, and save the salt and hash in a record for that user login in our database. 

The [https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet OWASP example] has a SQL credential table with the columns:
<li> LOGIN VARCHAR (100) PRIMARY KEY,
<li> PASSWORD VARCHAR (32),
<li> SALT VARCHAR (32)

<h4>Crypto parameters</h4>

So let's try PBKDF2. We'll leave Bcrypt and Scrypt for another day. Readers, please provide your opinions on these other options, and indeed PBKDF2, parameters and what-not presented here.

<pre>
public class Passwords {
    public static final String ALGORITHM = "PBKDF2WithHmacSHA1";
    public static final int ITERATION_COUNT = 8192;
    public static final int KEY_SIZE = 160;

    public static byte[] hashPassword(char[] password, byte[] salt)
            throws GeneralSecurityException {
        return hashPassword(password, salt, ITERATION_COUNT, KEY_SIZE);
    }

    public static byte[] hashPassword(char[] password, byte[] salt,
            int iterationCount, int keySize) throws GeneralSecurityException {
        PBEKeySpec spec = new PBEKeySpec(password, salt, iterationCount, keySize);
        SecretKeyFactory factory = SecretKeyFactory.getInstance(ALGORITHM);
        return factory.generateSecret(spec).getEncoded();
    }
    ...
</pre>

where we use <a href="http://docs.oracle.com/javase/7/docs/api/javax/crypto/spec/PBEKeySpec.html"><tt>PBEKeySpec</tt></a> and stuff.

We will have to revise the defaults for these parameters in future, as computing power increases. 

Let's test that this salting, hashing and matching actually works.
<pre>
    @Test
    public void test() throws Exception {
        char[] password = "12345678".toCharArray();
        byte[] salt = PasswordSalts.nextSalt();
        byte[] hash = Passwords.hashPassword(password, salt);
        assertTrue(Passwords.matches(password, hash, salt));
        byte[] otherSaltBytes = Arrays.copyOf(salt, salt.length);
        otherSaltBytes[0] ^= otherSaltBytes[0];
        assertFalse(Passwords.matches(password, hash, otherSaltBytes));
        assertFalse(Passwords.matches("wrong".toCharArray(), hash, salt));
    }
</pre>

where we use the following method to authenticate a supplied password, having retrieved the hash and salt from our database.

<pre>
    public static boolean matches(char[] password, byte[] passwordHash, byte[] salt) 
            throws GeneralSecurityException {
        return matches(password, passwordHash, salt, ITERATION_COUNT, KEY_SIZE);
    }

    public static boolean matches(char[] password, byte[] passwordHash, byte[] salt,
            int iterationCount, int keySize) throws GeneralSecurityException {
        return Arrays.equals(passwordHash, hashPassword(password, salt, 
                iterationCount, keySize));
    }
</pre>

where we check if the supplied password matches our hash with related salt, using the provided PBKDF2 parameters.

<h4>Computational effort</h4>

According to the <a href="https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet">OWASP Password Storage Cheat Sheet</a>,

<blockquote>
You should measure the time required and make sure that its as large as possible without providing a significantly noticeable delay when your users authenticate.
</blockquote>

Otherwise we should tweak the iteration count and key size.

So perhaps the time required to hash the password should be less than 100ms for consumer sites? I'm just guessing and don't really know so hopefully a reader can comment. In the case of secure admin sites, perhaps we are happier with it taking a bit longer.

<pre>
    @Test
    public void testEffort() throws Exception {
        String password = "12345678";
        long startMillis = System.currentTimeMillis();
        byte[] saltBytes = Passwords.nextSalt();
        Passwords.hashPassword(password, saltBytes);
        System.out.println("time " + Millis.elapsed(startMillis));
        if (Millis.elapsed(startMillis) < 10) {
            System.out.println("Ooooooo.... i'm not sure");
        } else if (Millis.elapsed(startMillis) > 500) {
            System.out.println("Ooooooo.... i don't know");
        }
    }
</pre>

Given that CPU power is increasing every year, we need the dynamic solution where we can revise the parameters. This will be presented in part 2. 

<h4>Furthermore</h4>

According to the <a href="https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet">OWASP Password Storage Cheat Sheet</a>,

<blockquote>
An additional password storage defense mechanism involves storing the salt in a different location than the password hash. Use of the server's filesystem is one commonly used mechanism for salt isolation, assuming the password hashes are stored in different location such as a database.
</blockquote>

So i guess the salt could be encrypted in the database, and this key loaded from a keystore by our application, i.e. off the filesystem. Our app uses this key to decrypt the salts retrieved from the database. In this case, both our database and filesystem need to be compromised, and password data and keystore both stolen, to effect password theft.

Rather than a keystore, let's specify a password in our application configuration, for the purpose of password-based encryption of the salt. This will be presented in Part 3. 

So we'll have a salt hard-coded in our source code, for a password which is specified as an application parameter on the filesystem, for the encryption of our logins' salted and hashed passwords stored in our database. This means our source code needs to be known, or jar stolen, together with the application configuration file, as well as the database content, in order to have a crack at our password hashes!

<h4>Conclusion</h4>

Passwords should never be seen or stored in clear text, or in any reversible fashion. 

Since the passwords that people manage to come up with are, urm, far from random, we add salt, to protect against rainbow attacks and what-not.

While SHA-2 is recommended these days for general hashing, we should use computationally expensive algorithms for password hashing, so that the passwords are harder to crack.

We present an implementation using <tt>PBKDF2WithHmacSHA1</tt>, which seems to be quite common according to some googling. 

The hashing operation should take as long as we are willing to make the user wait, perhaps a few hundred milliseconds. So we should tweak the algorithm parameters appropriately, i.e. the key size and number of iterations of the password-based key derivation function.

Coming up in part 2, we will cater for multiple revisions, to increase the number of iterations and key size, and illustrate how hashes might be migrated on the fly to the latest revision.

In part 3, we'll take a final step of encrypting the password salt in our database.

<img src='http://dingo.care2.com/pictures/greenliving/19/18268.large.jpg'>

<h4>Resources</h4>

https://code.google.com/p/vellum/ - where i will collate these articles and their code - e.g. see <a href="http://code.google.com/p/vellum/source/browse/trunk/src/vellum/crypto/Passwords.java"><tt>Passwords</tt></a>.
